P类问题、NP类问题、NPC问题、NP难问题

1. P类问题：能在多项式时间内可解的问题。

2. NP类问题：在多项式时间内“可验证”的问题。也就是说，不能判定这个问题到底有没有解，而是猜出一个解来在多项式时间内证明这个解是否正确。即该问题的猜测过程是不确定的，而对其某一个解的验证则能够在多项式时间内完成。P类问题属于NP问题，但NP类问题不一定属于P类问题。

3. NPC问题：存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。其定义要满足2个条件：

l 它是一个NP问题；

l 所有NP问题都能规约到它。

4. NP难问题：NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广，NP-Hard问题没有限定属于NP），即所有的NP问题都能约化到它，但是他不一定是一个NP问题。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。以上四个问题之间的关系如下图所示：

P=NP？

l 此处会再次从不同的角度来讨论P与NP的定义。

“P=NP?” 通常被认为是计算机科学最重要的问题。在很早的时候，就有个数学家毫不客气的指出，P=NP? 是个愚蠢的问题，并且为了嘲笑它，专门在4月1号写了一篇“论文”，称自己证明了 P=NP。

首先，我们要搞清楚什么是“P=NP?” 为此，我们必须先了解一下什么是“算法复杂度”。为此，我们又必须先了解什么是“算法”。我们可以简单的把“算法”想象成一台机器，就跟绞肉机似的。我们给它一些“输入”，它就给我们一些“输出”。比如，绞肉机的输入是肉末，输出是肉渣。牛的输入是草，输出是奶。“加法器”的输入是两个整数，输出是这两个整数的和。“算法理论”所讨论的问题，就是如何设计这些机器，让它们更加有效的工作。就像是说如何培育出优质的奶牛，吃进相同数量的草，更快的产出更多的奶。

世界上的计算问题，都需要“算法”经过一定时间的工作（也叫“计算”），才能得到结果。计算所需要的时间，往往跟“输入”的大小有关系。你的牛吃越是多的草，它就需要越是长时间才能把它们都变成奶。这种草和奶的转换速度，通常被叫做“算法复杂度”。算法复杂度通常被表示为一个函数f(n)，其中n是输入的大小。比如，如果我们的算法复杂度为n^2，那么当输入10个东西的时候，它需要100个单元的时间才能完成计算。当输入100 个东西的时候，它需要10000个单元的时间才能完成。当输入1000个数据的时候，它需要1000000个单元的时间。所谓的“P时间”，多项式时间，就是说这个复杂度函数f(n)是一个多项式。

“P=NP?”中的“P”，就是指所有这些复杂度为多项式的算法的“集合”，也就是“所有”的复杂度为多项式的算法。为了简要的描述以下的内容，我定义一些术语：

l “f(n)时间算法”=“能够在f(n)时间之内，解决某个问题的算法”

当f(n)是个多项式（比如n^2）的时候，这就是“多项式时间算法”（P时间算法）。当f(n)是个指数函数（比如2^n）的时候，这就是“指数时间算法”（EXPTIME算法）。很多人认为NP问题就是需要指数时间的问题，而NP跟EXPTIME，其实是风马牛不相及的。很显然，P不等于EXPTIME，但是P是否等于NP，却没有一个结论。

现在我来解释一下什么是NP。通常的计算机，都是确定性（deterministic）的。它们在同一个时刻，只有一种行为。如果用程序来表示，那么它们遇到一个条件判断（分支）的时候，只能一次探索其中一条路径。比如：

if (x == 0) {

    one();

}

else {

    two();

}

在这里，根据x的值是否为零，one()和two()这两个操作，只有一个会发生。然而，有人幻想出来一种机器，叫做“非确定性计算机”（nondeterministic computer），它可以同时运行这程序的两个分支，one()和two()。这有什么用处呢？它的用处就在于，当你不知道x的大小的时候，根据one()和two()是否“运行成功”，你可以推断出x是否为零。这种方式可以同时探索多种可能性。这不是普通的“并行计算”，因为每当遇到一个分支点，非确定性计算机就会产生新的计算单元，用以同时探索这些路径。这机器就像有“分身术”一样。当这种分支点存在于循环（或者递归）里面的时候，它就会反复的产生新的计算单元，新的计算单元又产生更多的计算单元，就跟细胞分裂一样。一般的计算机都没有 这种“超能力”，它们只有固定数目的计算单元。所以他只能先探索一条路径，失败之后，再回过头来探索另外一条。所以，它们似乎要多花一些时间才能得到结果。到这里，基本的概念都有了定义，于是我们可以圆满的给出P和NP的定义。P和NP是这样两个“问题的集合”：

l P = “确定性计算机”能够在“多项式时间”解决的所有问题

l NP = “非确定性计算机”能够在“多项式时间”解决的所有问题（注意它们的区别，仅在于“确定性”或者是“非确定性”。）

“P=NP?”问题的目标，就是想要知道P和NP这两个集合是否相等。为了证明两个集合（A和 B）相等，一般都要证明两个方向：

1. A 包含 B；

2. B 包含 A。

上一个标题中我们已经说过NP包含了P。因为任何一个非确定性机器，都能被当成一个确定性的机器来用。你只要不使用它的“超能力”，在每个分支点只探索一条路径就行。所以“P=NP?”问题的关键，就在于P是否也包含了NP。也就是说，如果只使用确定性计算机，能否在多项式时间之内，解决所有非确定性计算机能在多项式时间内解决的问题。

我们来细看一下什么是多项式时间（Polynomial time）。我们都知道，n^2是多项式，n^{1000000}也是多项式。多项式与多项式之间，却有天壤之别。把解决问题所需要的时间，用“多项式”这么笼统的概念来描述，其实是非常不准确的做法。在实际的大规模应用中，n^2的算法都嫌慢。能找到“多项式时间”的算法，根本不能说明任何问题。对此，理论家们喜欢说，就算再大的多项式(比如 n^{1000000})，也不能和再小的指数函数（比如 1.0001^n）相比。因为总是“存在”一个M，当n>M的时候，1.0001^n会超过n^{1000000}。可是问题的关键，却不在于M的“存在”，而在于它的“大小”。如果你的输入必须达到天文数字才能让指数函数超过多项式的话，那么还不如就用指数复杂度的算法。所以，“P=NP?”这问题的错误就在于，它并没有针对我们的实际需要，而是首先假设了我们有“无穷大”的输入，有“无穷多”的时间和耐心，可以让多项式时间的算法“最终”得到优势。

精选资料：

钟哥数学博士团队介绍：      团队是由国内数学“一流学科”博士组成，接受了国内顶尖教授导师的培养，数学专业知识扎实、素质过硬，博士团队有着丰富的数学（高代、数分等）基础课程的教学经验，以及数学资料的研发与制作经验。   
    高代学习QQ交流群：945166269. 加入高代数分交流微信群请加助手微信：zhongyuemingmit

让我知道你在看

获取更多资料，请点击左下角的“阅读原文”